home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1990 / 11 / e_floyd / applicat.txt < prev    next >
Text File  |  1990-07-24  |  8KB  |  152 lines
  1. Applications
  2.  
  3. Spelling Checker:
  4.  
  5. With superimposed coding, we can build a spelling checker that
  6. has some unusual properties.  First, use the results of one of
  7. the studies of word usage frequency to build a "primary"
  8. dictionary bit table from the 10000 most frequently used English
  9. words.  At 13 bits per key, the optimal bit table will occupy
  10. about 23k bytes and will have a false drop probability of about
  11. 1/8000.  Then, partition the remaining words by first letter into
  12. lists of 10000 or fewer words.  Create a "secondary" bit table
  13. for each partition and save it on disk.  The spelling checker
  14. program can keep the primary bit table in memory and can allocate
  15. an auxiliary, 23k buffer for one of the secondary tables.  The
  16. program will find most words in the primary bit table.  For rare
  17. or misspelled words, the program will usually have to read a bit
  18. table from disk into the auxiliary buffer.  Still, it should be
  19. fast enough to keep up with real-time typing.  Overall, the
  20. checker will fail to catch about 1/4000 misspelled words, the
  21. same as Doug McIlroy's program.  
  22.  
  23. Now we have a complete, conventional spelling checker with good
  24. accuracy, but small enough (under 60k) to reside constantly in
  25. memory, perhaps as a DOS TSR.  If we allocate a primary bit table
  26. for 12000 words (28k), the program will be capable of learning up
  27. to 2000 new words without compromising its design target for
  28. accuracy.
  29.  
  30. Document retrieval:
  31.  
  32. To help researchers locate information, electronic libraries
  33. index documents and abstracts by author and subject keyword
  34. search terms.  Sometimes as many as ten search terms are
  35. associated with a single document.  Instead of a conventional
  36. index, we can use superimposed coding to speed up the search. 
  37. Build for each document a small bit table superimposing five bits
  38. for each index term.  This bit table is sometimes called a
  39. "surrogate" or "signature"; I'll call it a surrogate.  The
  40. surrogate may be quite small, say 128 bits.  The false drop rate
  41. for a 128-bit surrogate with ten, 5-bit keywords is less than
  42. (50/128)@SUPERSCRIPT[5], or 1/110.  Let's say we want to locate all the
  43. documents associated with the keyword "programmer".  We could
  44. test each surrogate for the keyword as described above.  However,
  45. there's no need to recompute the hash function and bit positions
  46. for the search keyword each time.  Instead, build a 128-bit
  47. search table, like a surrogate but with only the 5 bits "on" for
  48. the single word "programmer".  If a document surrogate has even
  49. one bit "off" that is "on" in the search table, the document
  50. can't possibly be associated with the keyword "programmer".  We
  51. can compare the search table with each surrogate using Boolean
  52. logic: Perform a logical "AND" between each document's surrogate
  53. and the search table and compare the result to the original
  54. search table.  If they are not equal, we can reject the document
  55. immediately.  If they are equal, we must investigate the documentèfurther to determine whether or not it is associated with the
  56. search term.
  57.  
  58.   1001011000101.. Surrogate for document 1
  59.   0001001001000.. Search table
  60.   ───────────── AND
  61.   0001001000000.. Reject document 1
  62.            ^
  63.   0010010111010.. Surrogate for document 2
  64.   0001001001000.. Search table
  65.   ───────────── AND
  66.   0000000001000.. Reject document 2
  67.      ^  ^
  68.   0101011011010.. Surrogate for document 3
  69.   0001001001000.. Search table
  70.   ───────────── AND
  71.   0001001001000.. Investigate document 3 
  72.  
  73. If we want to search for a conjunction of two terms, say
  74. "programmer" AND "sociopath", the same technique applies.  Build
  75. a search table with bits for both terms.  With each surrogate,
  76. perform the logical "AND" and compare.  This time, all ten bits
  77. in the search table must also be "on" in the document table.  The
  78. false drop probability is now about (1/110)*(1/110), or 1/12100. 
  79. So, the search becomes more efficient as we search for more
  80. conjoined terms.
  81.  
  82. To search for a disjunction of two terms, say "programmer" OR
  83. "hacker", we must build two search tables and investigate further
  84. any document whose surrogate satisfies either search.  The false
  85. drop probability, therefore, is half the probability of a
  86. single-term search, or about 1/55.  By extending these
  87. techniques, we can construct complex queries.  One shortcoming -
  88. we can't use surrogates to speed up negation (NOT) in a query. 
  89. Fortunately, in document retrieval, negation is frequently
  90. associated with positive conditions that restrict the set of
  91. documents anyway.
  92.  
  93. Finally, we can save search time by employing a peculiar
  94. "sideways" ordering of surrogate bits.  Gather together all the
  95. first bits from a group of surrogates and store them in document
  96. order at the beginning of the surrogate file.  Follow this with
  97. all the second bits, and so on.  Think of the file as columns of
  98. surrogate bits.  Now we can search the group of document
  99. surrogates in parallel.  Simply "AND" together the bit columns
  100. corresponding to the "on" bits in the search table and the result
  101. is a bit map whose "on" bits correspond to documents that we must
  102. investigate further.  If we block surrogates in groups of 4096
  103. documents, each bit column will occupy 512 bytes - one sector on
  104. many modern disk subsystems.  This kind of grouping simplifies
  105. calculations and optimizes hardware performance for bit column
  106. retrieval.  In the example fragment shown below, for instance, it
  107. is necessary to read only the fourth, seventh, and tenth sectors
  108. of the surrogate file to compute a bit map for the first 4k
  109. documents. è
  110.     0 0 0 1 0 0 1 0 0 1 0 0 0... Search table
  111. Sur       | AND | AND |          =  Bit Map
  112. ---       V     V     V             -------
  113. 1.  1 0 0 1 0 1 1 0 0 0 1 0 1...    0 Reject
  114. 2.  0 0 1 0 0 1 0 1 1 1 0 1 0...    0 Reject
  115. 3.  0 1 0 1 0 1 1 0 1 1 0 1 0...    1 Investigate
  116. 4.  0 1 1 0 0 0 1 1 0 0 0 0 1...    0 Reject
  117. 5.  1 0 0 1 0 0 1 0 1 1 0 0 1...    1 Investigate
  118. .         .     .     .             .
  119. .         .     .     .             .
  120.  
  121. Database:
  122.  
  123. We can use surrogate files instead of conventional indices in
  124. database applications, also. For example, consider a
  125. million-record database with fifty fields in each record.  The
  126. average  size of each field is 10 bytes, so the database size is
  127. about 500 megabytes.  We want to index the database on all fifty
  128. fields.  As an optimistic estimate, a conventional index would
  129. require about 15 megabytes for each field for a minimum total
  130. index size of 750 megabytes.  The index is larger than the
  131. database.  On the other hand, an optimal surrogate for 50 keys at
  132. 10 bits per key is about 90 bytes for a total surrogate file size
  133. of 90 megabytes.  The surrogate file is almost an order of
  134. magnitude smaller than a conventional index.  It is likely to be
  135. slower than a conventional index for single-field queries. 
  136. However, for complex queries involving Boolean combinations of
  137. field values, it can be considerably faster than an conventional
  138. index.  (Implementation note: Distinguish between fields by
  139. prefixing each field value with a domain identifier before
  140. hashing bits for the surrogate.)
  141.  
  142. When the database is fairly stable and a large proportion of
  143. queries against the index result in a record-not-found condition,
  144. a superimposed code dictionary can save time.  For example,
  145. consider a 10000 record database indexed on one field.  A
  146. superimposed code dictionary for 10000 keys with 10 bits per key
  147. is about 18k bytes - small enough to hold in memory.  Before
  148. searching the index for a key, check for its existence in the
  149. dictionary.  If it's not in the dictionary, there's no need to
  150. search the index.  We will have reduced unnecessary index
  151. searches by a factor of a thousand. 
  152.